package com.explorati.dongtaiguihua.fibonaccisequence;

/**
 * 斐波那锲数列 动态规划基础
 * 
 * 问题：当n为40多的时候就已经耗费很长的时间
 * 
 * 时间复杂度 指数级
 * 
 * 优化一：记忆化搜索-自上而下的解决问题  一个全局的数组，省去了重复计算
 * 
 * @author explorati
 *
 */
public class Solution {

	static int[] memo;
	static int num = 0;

	// 记忆化搜索
	public static int fibonacci(int n) {
		num++;
		if (n == 0) {
			return 0;
		}
		if (n == 1) {
			return 1;
		}
		if (memo[n] == -1) {
			memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
		}

		return memo[n];
	}

	public static void main(String[] args) {
		num = 0;
		int n = 40;
		memo = new int[n + 1];
		for (int i = 0; i < memo.length; i++) {
			memo[i] = -1;
		}

		long startTime = System.nanoTime();
		int res = fibonacci(n);
		long endTime = System.nanoTime();
		System.out.println("fibonacci(" + n + ") =" + res);
		System.out.println("time : " + (endTime - startTime) / 1000000000.0 + "s");
		System.out.println("run fnction fibonacci() " + num + "times.");
	}
}
